/*
深度遍历--二叉树
连接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/
题目：230. 二叉搜索树中第K小的元素




简介：递归解题

算法思路：
上述解法不仅使⽤⼤量额外空间存储数据，并且会将所有的结点都遍历⼀遍。
但是，我们可以根据中序遍历的过程，只需扫描前 k 个结点即可。
因此，我们可以创建⼀个全局的计数器 count，将其初始化为 k，每遍历⼀个节点就将 count--。直到
某次递归的时候，count 的值等于 1，说明此时的结点就是我们要找的结果。
比特就业课
算法流程：
1. 定义⼀个全局的变量 count，在主函数中初始化为 k 的值（不⽤全局也可以，当成参数传⼊递归过
程中）；
递归函数的设计：int dfs(TreeNode* root)：
• 返回值为第 k 个结点；
递归函数流程（中序遍历）：
1. 递归出⼝：空节点直接返回 -1，说明没有找到；
2. 去左⼦树上查找结果，记为 retleft：
a. 如果 retleft == -1，说明没找到，继续执⾏下⾯逻辑；
b. 如果 retleft != -1，说明找到了，直接返回结果，⽆需执⾏下⾯代码（剪枝）；
3. 如果左⼦树没找到，判断当前结点是否符合：
a. 如果符合，直接返回结果
4. 如果当前结点不符合，去右⼦树上寻找结果。


*/
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int count=0;
    int ret=0;
    int kthSmallest(TreeNode* root, int k) {
        count=k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if(root==nullptr)
            return;
        dfs(root->left);
        //减枝
        if(count==0)    return ;
        count--;
        if(count==0)
        {
            ret = root->val;
            return ;
        }
        dfs(root->right);
    }
};